백준 10775번

오늘 풀어본 문제는 백준의 10775번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 5

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 $G$ 개의 게이트가 있으며 각각은 $1$ 에서 $G$ 까지의 번호를 가지고 있다.

공항에는 $P$ 개의 비행기가 순서대로 도착할 예정이며, 당신은 $i$ 번째 비행기를 $1$ 번부터 $g_i$ $(1 \le g_i \le G)$ 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 $G$ $(1 \le G \le 10^5)$ 가 주어진다.

두 번째 줄에는 비행기의 수 $P$ $(1 \le P \le 10^5)$ 가 주어진다.

이후 $P$ 개의 줄에 $g_i$ $(1 \le g_i \le G)$ 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

풀이과정

1번째 시도

문제를 해결하기 위해서 생각한 것은 그리디 알고리즘으로, 게이트의 번호가 작을 수록 수용할 수 있는 종류가 다양하기 때문에 우선적으로 들어오는 비행기들은 가능한한 가장 큰 게이트의 번호를 할당하는 방식을 생각하였다.

문제는 할당해줄 수 있는 가장 큰 게이트를 찾는 것이었는데, 매번 탐색하여 찾는 것은 시간 초과가 발생할 수 있기 때문에 DisjointSet 을 활용하기로 하였다. 앞의 번호와 현재 번호를 Union 하여 Find 를 이용하여 사용 가능한 가장 큰 번호의 게이트를 얻는 방식을 생각한 것이다.

지난번에 분리 집합을 사용하는 문제에서 기존의 DisjointSet 에서 rank 를 없애고 숫자의 대소비교를 이용했는데, 이번 문제를 풀면서 인자를 하나 더 제공하여 원한다면 랭크를 미리 오름차순이나 내림차순으로 줄 수 있도록 설정하였다.

코드는 다음과 같이 작성하였다.

disjoint_set.hpp

#ifndef __DISJOINT_SET_HPP__
#define __DISJOINT_SET_HPP__

#include <vector>

class DisjointSet {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    DisjointSet(int n, int order = 0) {
        parent.resize(n);
        rank.resize(n, 0);

        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = i * order;
        }
    }

    int find(int u) {
        if (u == parent[u]) {
            return u;
        }
        else {
            return parent[u] = find(parent[u]);
        }
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);

        if (u != v) {
            if (rank[u] > rank[v]) {
                std::swap(u, v);
            }

            parent[u] = v;

            if (rank[u] == rank[v]) {
                rank[v]++;
            }
        }
    }
};

#endif // !__DISJOINT_SET_HPP__

main.cpp

#include <bits/stdc++.h>
#include "disjoint_set.hpp"

using namespace std;

using ll = long long;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int G, P;
    cin >> G >> P;

    vector<int> g(P, 0);
    for (int i=0; i<P; i++) {
        cin >> g[i];
    }

    DisjointSet diset(G+1, -1);
    int result = 0;

    for (int i=0; i<P; i++) {
        int gate = diset.find(g[i]);
        if (gate != 0) {
            result++;
            diset.merge(gate - 1, gate);
        }
        else {
            break;
        }
    }

    cout << result;

    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

확실히 CLASS 5 문제들에서 DisjointSet 을 활용하는 문제들이 많이 보이는 것 같다. 앞으로 11문제 정도 남았으니, 한 두 문제 정도는 DisjointSet 을 활용하는 문제가 나올 것 같은데 과연 어떨지 궁금하다.

여담으로 내가 만든 DisjointSet 자료구조는 내 깃헙 레포지토리²에서 확인할 수 있다. 필요한 사람은 참고하길 바란다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/10775
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C++/custom_data_structures/disjoint_set.hpp

← Previous Post Next Post →